/* 
 * search in Roteated Sorted Array
 * (0 1 2 3 4 5) (3 4 5 0 1 2)
 */

#include "../../func.h"

int search(vector<int> &nums, int targ)
{
    int first = 0, last = nums.size();
    while (first != last)
    {
        const int mid = first + (last - first) / 2;
        if (nums[mid] == targ)
            return mid;
        if (nums[first] <= nums[mid])
        {
            if (nums[first] <= targ && targ < nums[mid])
                last = mid;
            else
                first = mid + 1;
        }
        else
        {
            if (nums[mid] < targ && targ <= nums[last - 1])
                first = mid + 1;
            else
                last = mid;
        }
    }
}